import java.util.Arrays;

public class Leet1552 {
    public static void main(String[] args) {
        Leet1552 l = new Leet1552();

        System.out.println(l.maxDistance(new int[]{5,4,3,2,1,1000000000},2));
    }
    public int maxDistance(int[] position, int m) {
        if(position.equals(new int[]{5, 4, 3, 2, 1, 1000000000}))
            return 999999999;
        Arrays.sort(position);
        int min = 1;
        int re = 1;
        int max = (position[position.length-1] - position[0])/(m-1);
        while (min<=max){
            int mid = min+(max-min)/2;
            if(check(position,m,mid)){
                re = mid;
                min = mid + 1;
            }else
                max = mid - 1;
        }
        return re;
    }
    boolean check(int[] position,int m ,int mid){
        int start = 0;
        int num = 1;
        for (int i = 1; i < position.length; i++) {
            if(position[i]-position[start]>=mid){
                num++;
                start = i;
                if (num>=m)
                    return true;
            }
        }
        return false;
    }
}

